package offer;

import java.util.Arrays;

/**
 * @author LongYongjiang
 */
@FunctionalInterface
public interface NumRollsToTarget {
    /**
     * 这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
     * 给定三个整数 n , k 和 target ，返回可能的方式(从总共 kn 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。
     * 答案可能很大，你需要对 109 + 7 取模 。
     * @param n             骰子数量
     * @param k             骰子面数
     * @param target        给定数字和
     * @return              可能数量
     */
    int numRollsToTarget(int n, int k, int target);
}
class NumRollsToTargetTest{
    private static final int TEST_01_N = 30;
    private static final int TEST_01_K = 30;
    private static final int TEST_01_TARGET = 500;

    public static void main(String[] args) {
        new NumRollsToTargetImpl1().numRollsToTarget(TEST_01_N, TEST_01_K, TEST_01_TARGET);
    }
}

/**
 * 暴力解法
 */
class NumRollsToTargetImpl1 implements NumRollsToTarget{

    private static final int MODULE = (int)1e9 + 7;
    @Override
    public int numRollsToTarget(int n, int k, int target) {

        int[] dices = new int[n];
        Arrays.fill(dices, 1);
        int ans =dfs(dices, n, k, 0, target);
        return ans % MODULE;
    }
    private int dfs(int[] dices, int n, int k, int cur,int target){
        if(cur < n){
            int sum = 0;
            for(int i = 1; i <= k; i++){
                dices[cur] = i;
                sum += dfs(dices, n, k, cur + 1, target);
            }
            return sum;
        }else if(cur == n){
            return Arrays.stream(dices).sum() == target ? 1 : 0;
        }else {
            return 0;
        }
    }
}
class NumRollsToTargetImpl2 implements NumRollsToTarget{

    private static final int MODULE = (int)1e9 + 7;
    @Override
    public int numRollsToTarget(int n, int k, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 0; i < n; i++){
            for(int j = target; j >= 0; j--){
                dp[j] = 0;
                for(int m = 1; m <= k; m++){
                    if(j > m){
                        dp[j] = (dp[j] + dp[j - m]) % MODULE;
                    }
                }
            }
        }
        return dp[target];
    }

}
